/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */

// @lc code=start
class Solution
{
public:
    void solveSudoku(vector<vector<char>> &board)
    {
        vector<vector<int>> row(9, vector<int>(9, 0));
        vector<vector<int>> col(9, vector<int>(9, 0));
        vector<vector<int>> block(9, vector<int>(9, 0));
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '1';
                    int block_id = i / 3 * 3 + j / 3;
                    row[i][num] = 1;
                    col[j][num] = 1;
                    block[block_id][num] = 1;
                }
            }
        }
        solve(board, row, col, block, 0, 0);
    }

    bool solve(vector<vector<char>> &board,
               vector<vector<int>> &row,
               vector<vector<int>> &col,
               vector<vector<int>> &block, int i, int j)
    {

        {
            bool falg = false;
            while (i < 9 && !falg)
            {
                for (; j < 9; ++j)
                {
                    if (board[i][j] == '.')
                    {
                        falg = true;
                        break;
                    }
                }
                if (j == 9)
                {
                    ++i;
                    j = 0;
                }
            }
        }

        if (i == 9)
            return true;

        if (board[i][j] == '.')
        {
            //需要对当前位置进行填充
            for (int k = 0; k < 9; k++)
            {
                if (row[i][k] == 0 && col[j][k] == 0 && block[i / 3 * 3 + j / 3][k] == 0)
                {
                    row[i][k] = 1;
                    col[j][k] = 1;
                    block[i / 3 * 3 + j / 3][k] = 1;
                    board[i][j] = '1' + k;
                    if (solve(board, row, col, block, i, j + 1))
                        return true;
                    row[i][k] = 0;
                    col[j][k] = 0;
                    block[i / 3 * 3 + j / 3][k] = 0;
                    board[i][j] = '.';
                }
            }
        }
        return false;
    }
};
// @lc code=end
